package program.sort;

import com.alibaba.fastjson.JSONObject;

/**
 * 冒泡排序
 *
 * @author luxx
 * @date 2018/4/28 0028
 */
public class BubbleSort {

    static void bubbleSort(int[] array) {
        //外层循环控制排序趟数
        for (int i = 0; i < array.length; i++) {
            //内层循环控制每一趟排序多少次
            for (int j = 1; j < array.length - i; j++) {
                int temp;
                if (array[j - 1] > array[j]) {
                    temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                }
            }
        }
        System.out.println(JSONObject.toJSONString(array));
    }

    /**
     * 优化后的冒泡排序
     */
    static void bubbleSort2(int[] array) {
        int k;

        //flag代表最后交换的位置，默认为最大值
        int flag = array.length;

        //如果flag=0代表本次没有交换，意味着顺序已经正确
        while (flag > 0) {
            k = flag;
            flag = 0;

            for (int j = 1; j < k; j++) {
                //前面的数字大于后面的数字就交换
                if (array[j - 1] > array[j]) {
                    int temp;
                    temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;

                    //记录最后一次交换的位置
                    flag = j;
                }
            }
        }
        System.out.println(JSONObject.toJSONString(array));
    }

    public static void main(String[] args) {
        bubbleSort2(new int[]{8, 5, 2, 1, 6, 3, 7, 11, 66, 33, 22, 88, 13, 12, 56});
    }
}
